package puzzle.projecteuler.p200;

import astudy.util.AdvMath;
import astudy.util.AdvMath.Factors;

public class Problem108C {

	/**
	 * n = p1^a1 * ... * pm^am
	 * the number of solution is [(2a1+1)*...*(2am+1)+1]/2
	 * 
	 * answer	: 180180
	 * time cost: 1750 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		int n = 1;
		while (true) {
			if (sn(n) < 1000) {
				n ++;
			} else {
				System.out.println(n);
				break;
			}
		}
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}

	public static int sn(long n) {
		Factors fs = AdvMath.factor(n);
		int c = 1;
		for (long k: fs.keySet()) {
			c *= (2*fs.get(k)+1);
		}
		return (c+1)/2;
	}
}
